Search for: All records

Transposon-encoded tnpB and iscB genes encode RNA-guided DNA nucleases that promote their own selfish spread through targeted DNA cleavage and homologous recombination1–4. These widespread gene families were repeatedly domesticated over evolutionary timescales, leading to the emergence of diverse CRISPR-associated nucleases including Cas9 and Cas12 (refs. 5,6). We set out to test the hypothesis that TnpB nucleases may have also been repurposed for novel, unexpected functions other than CRISPR–Cas adaptive immunity. Here, using phylogenetics, structural predictions, comparative genomics and functional assays, we uncover multiple independent genesis events of programmable transcription factors, which we name TnpB-like nuclease-dead repressors (TldRs). These proteins use naturally occurring guide RNAs to specifically target conserved promoter regions of the genome, leading to potent gene repression in a mechanism akin to CRISPR interference technologies invented by humans7. Focusing on a TldR clade found broadly in Enterobacteriaceae, we discover that bacteriophages exploit the combined action of TldR and an adjacently encoded phage gene to alter the expression and composition of the host flagellar assembly, a transformation with the potential to impact motility8, phage susceptibility9, and host immunity10. Collectively, this work showcases the diverse molecular innovations that were enabled through repeated exaptation of transposon-encoded genes, and reveals the evolutionary trajectory of diverse RNA-guided transcription factors. RNA-guided transcription factors arose repeatedly via the domestication of transposon-encoded tnpB genes, representing a parallel evolutionary path to CRISPR-Cas adaptive immunity. 

TnpB nucleases represent the evolutionary precursors to CRISPR-Cas12 and are widespread in all domains of life. IS605-family TnpB homologs function as programmable RNA-guided homing endonucleases in bacteria, driving transposon maintenance through DNA double-strand break–stimulated homologous recombination. In this work, we uncovered molecular mechanisms of the transposition life cycle of IS607-family elements that, notably, also encode group I introns. We identified specific features for a candidate “IStron” fromClostridium botulinumthat allow the element to carefully control the relative levels of spliced products versus functional guide RNAs. Our results suggest that IStron transcripts evolved an ability to balance competing and mutually exclusive activities that promote selfish transposon spread while limiting adverse fitness costs on the host. Collectively, this work highlights molecular innovation in the multifunctional utility of transposon-encoded noncoding RNAs. 

Insertion sequences are compact and pervasive transposable elements found in bacteria, which encode only the genes necessary for their mobilization and maintenance1. IS200- and IS605-family transposons undergo ‘peel-and-paste’ transposition catalysed by a TnpA transposase2, but they also encode diverse, TnpB- and IscB-family proteins that are evolutionarily related to the CRISPR-associated effectors Cas12 and Cas9, respectively3,4. Recent studies have demonstrated that TnpB and IscB function as RNA-guided DNA endonucleases5,6, but the broader biological role of this activity has remained enigmatic. Here we show that TnpB and IscB are essential to prevent permanent transposon loss as a consequence of the TnpA transposition mechanism. We selected a family of related insertion sequences from Geobacillus stearothermophilus that encode several TnpB and IscB orthologues, and showed that a single TnpA transposase was broadly active for transposon mobilization. The donor joints formed upon religation of transposon-flanking sequences were efficiently targeted for cleavage by RNA-guided TnpB and IscB nucleases, and co-expression of TnpB and TnpA led to substantially greater transposon retention relative to conditions in which TnpA was expressed alone. Notably, TnpA and TnpB also stimulated recombination frequencies, surpassing rates observed with TnpB alone. Collectively, this study reveals that RNA-guided DNA cleavage arose as a primal biochemical activity to bias the selfish inheritance and spread of transposable elements, which was later co-opted during the evolution of CRISPR–Cas adaptive immunity for antiviral defence. TnpB and IscB nucleases use transposon-encoded guide RNAs to target genomic sequences for cleavage, thereby favouring copying and spreading of transposable elements. 

A gap exists between the theory of EDF scheduling on identical multiprocessors with arbitrary processor affinities (APA) and practical EDF scheduling as embodied by the SCHED_DEADLINE (SD) scheduler in Linux. This is because the EDF variant proposed in theory for APA, called Strong APA EDF, introduces affinity-related complexities that are not applicable under global EDF, the original target of SD. SD instead treats affinities as a secondary concern. It is shown herein that this treatment comes at the price of causing SD to be fundamentally broken with regard to soft real-time (SRT)- optimality with APA. This result resolves a longstanding open question regarding this matter. It also suggests that Strong APA EDF, which has been proven to be SRT-optimal, is necessary for practical EDF scheduling with APA. However, non-preemptive sections are typically required in practice, and prior work on Strong APA EDF is limited to fully preemptive systems. In this paper, this prior work is extended for the first time to deal with non-preemptivity, which introduces non-trivial nuances with APA. As a byproduct of considering non-preemptivity, it is shown that the SRT-optimality of EDF in this context carries over to a significantly expanded class of schedulers 

Prior work has shown that the global earliest-deadline-first (GEDF) scheduler is soft real-time (SRT)-optimal for sporadic task systems in a variety of contexts, meaning that bounded deadline tardiness can be guaranteed under it for any task system that does not cause platform overutilization. However, one particularly compelling context has remained elusive: multiprocessor platforms in which tasks have affinity masks that determine the processors where they may execute. Actual GEDF implementations, such as the SCHED_DEADLINE class in Linux, have dealt with this unresolved question by foregoing SRT guarantees once affinity masks are set. This unresolved question, as it pertains to SCHED_DEADLINE, was included by Peter Zijlstra in a list of important open problems affecting Linux in his keynote talk at ECRTS 2017. In this paper, this question is resolved along with another open problem that at first blush seems unrelated but actually is. Specifically, both problems are closed by establishing two results. First, a proof strategy used previously to establish GEDF tardiness bounds that are exponential in size on heterogeneous uniform multiprocessors is generalized to show that polynomial bounds exist on a wider class of platforms. Second, both uniform multiprocessors and identical multiprocessors with affinities are shown to be within this class. These results yield the first polynomial GEDF tardiness bounds for the uniform case and the first such bounds of any kind for the identical-with-affinities case.